import java.util.ArrayList;
import java.util.List;

public class Algorithme {

	/**
	 * Structure : R = Root, E = Element EnTete, 1 = Element Simple
	 * 
	 * 			 {   POSITIONS  }
	 *   { PIECE }
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =R=E=E=E=E=E=E=E=E=E=E=E=E=		Matrice associée
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=1=1=1=╬=╬=╬=╬=╬=		0 0 0 1 1 1 1 0 0 0 0 0
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=╬=1=1=1=╬=╬=╬=╬=		0 0 0 1 0 1 1 1 0 0 0 0
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=╬=╬=1=1=1=╬=╬=╬=		0 0 0 1 0 0 1 1 1 0 0 0
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=╬=╬=╬=1=1=1=╬=╬=		0 0 0 1 0 0 0 1 1 1 0 0
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=╬=╬=╬=╬=1=1=1=╬=		0 0 0 1 0 0 0 0 1 1 1 0
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * =E=╬=╬=╬=1=╬=╬=╬=╬=╬=1=1=1=		0 0 0 1 0 0 0 0 0 1 1 1
	 *  ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║		
	 * 
	 */
	private Matrice matrice;
	private List<int[]> piecePlace;
	private List<List<Element>> solutions;
	private int ligne;
	private int colonne;
	
	public Algorithme(int ligne, int colonne) {
		piecePlace = new ArrayList<int[]>();
		this.ligne = ligne;
		this.colonne = colonne;
	}
	
	private void initMatrice() {
		matrice = new Matrice(ligne, colonne, piecePlace);
	}
	
	/**
	 * Fonction qui initialise la matrice en fonction des pièces et des cases
	 */

	private List<Element> creerEnTetesColonne(Element root, int cols) {
		List<Element> enTetes = new ArrayList<Element>();

	    Element predecesseur = root;
	    for (int i = 0; i < cols; ++i) {
	    	Element e = new Element();
	        e.setGauche(predecesseur);
	        e.setDroit(root);
	        enTetes.add(e);

	        root.setGauche(e);
	        predecesseur.setDroit(e);

	        predecesseur = e;
	    }

	    return enTetes;
	}

	private List<Element> creerEnTetesLigne(Element root, int lignes) {
		List<Element> enTetes = new ArrayList<Element>();

	    Element predecesseur = root;
	    for (int i = 0; i < lignes; i++) {
	        Element e = new Element();
	        e.setHaut(predecesseur);
	        e.setBas(root);
	        enTetes.add(e);

	        root.setHaut(e);
	        predecesseur.setBas(e);

	        predecesseur = e;
	    }

	    return enTetes;
	}

	private void supEnTetesLigne(List<Element> enTetes) {
	    for (Element enTete : enTetes) {
	        enTete.getGauche().setDroit(enTete.getDroit());
	        enTete.getDroit().setGauche(enTete.getGauche());
	        enTete.getHaut().setBas(enTete.getBas());
	        enTete.getBas().setHaut(enTete.getHaut());
	    }
	}

	private Element prochaineColonne(Element root)  {
	    int min = Integer.MAX_VALUE;

	    Element courent = root.getDroit();
	    Element prochain = courent;

	    while (courent != root) {
	        if (courent.getDonnee() < min) {
	            min = courent.getDonnee();
	            prochain = courent;
	        }
	        courent = courent.getDroit();
	    }

	    return prochain;
	}

	private void supElement(Element enTete) {
	    enTete.getGauche().setDroit(enTete.getDroit());
	    enTete.getDroit().setGauche(enTete.getGauche());

	    Element col = enTete.getBas();
	    while (col != enTete) {
	        Element ligne = col.getDroit();
	        while (ligne != col) {
	            ligne.getHaut().setBas(ligne.getBas());
	            ligne.getBas().setHaut(ligne.getHaut());
	            ligne.getEnTete().moins();
	            ligne = ligne.getDroit();
	        }
	        col = col.getBas();
	    }
	}

	private void reinsertElement(Element enTete) {
	    Element col = enTete.getHaut();

	    while (col != enTete) {
	        Element ligne = col.getGauche();
	        while (ligne != col) {
	            ligne.getHaut().setBas(ligne);
	            ligne.getBas().setHaut(ligne);
	            ligne.getEnTete().plus();
	            ligne = ligne.getGauche();
	        }
	        col = col.getHaut();
	    }

	    enTete.getGauche().setDroit(enTete);
	    enTete.getDroit().setGauche(enTete);
	}

	private Element creerMatriceCouverture(List<List<Integer>> matrix)  {
	    Element root = new Element();

	    List<Element> enTetesLigne = creerEnTetesLigne(root, matrix.size());
	    List<Element> enTetesColonne = creerEnTetesColonne(root, matrix.get(0).size());

	    for (int ligne = 0; ligne < matrix.size(); ligne++) {
	        Element ligne_first = enTetesLigne.get(ligne);
	        Element ligne_last = enTetesLigne.get(ligne);

	        for (int col = 0; col < matrix.get(0).size(); col++) {
	            if (matrix.get(ligne).get(col) == 1) {
	                Element enTete = enTetesColonne.get(col);

	                Element element = new Element(enTete, enTete.getHaut(), enTete, ligne_last, ligne_first, null, ligne);

	                element.getHaut().setBas(element);
	                element.getGauche().setDroit(element);

	                enTete.setHaut(element);
	                enTete.plus();

	                ligne_first.setGauche(element);
	                ligne_last = element;
	            }
	        }
	    }

	    supEnTetesLigne(enTetesLigne);

	    return root;
	}

	private boolean resolution(Element root, List<Element> couverture) {
		boolean isResolu = false;
	    Element enTete = prochaineColonne(root);

	    if (enTete == root) {
	        return true;
	    }

	    supElement(enTete);

	    Element colonneElement = enTete.getBas();
	    while (colonneElement != enTete) {
	        Element ligne_element = colonneElement.getDroit();
	        while (ligne_element != colonneElement) {
	            supElement(ligne_element.getEnTete());
	            ligne_element = ligne_element.getDroit();
	        }

	        isResolu = resolution(root, couverture);

	        ligne_element = colonneElement.getGauche();
	        while (ligne_element != colonneElement) {
	            reinsertElement(ligne_element.getEnTete());
	            ligne_element = ligne_element.getGauche();
	        }

	        if (isResolu) {
	            couverture.add(colonneElement);
	            break;
	        }

	        colonneElement = colonneElement.getBas();
	    }

	    reinsertElement(enTete);
	    return isResolu;
	}
	
	private void supprimerLigne(Element element) {
		Element ligneElement = element.getDroit();
        while (ligneElement != element) {
        	ligneElement.getHaut().setBas(ligneElement.getBas());
	        ligneElement.getBas().setHaut(ligneElement.getHaut());
	        ligneElement.getEnTete().moins();
            ligneElement = ligneElement.getDroit();
        }
        element.getHaut().setBas(element.getBas());
        element.getBas().setHaut(element.getHaut());
        element.getEnTete().moins();
        element = element.getDroit();
	}

	private int resoudre(List<List<Integer>> matrix) {
	    List<Element> couverture = new ArrayList<Element>();
	    Element root;
	    int nb = 0;

	    root = creerMatriceCouverture(matrix);
	    for(int i=0; i<ligne*colonne; i++) {
	    	if(resolution(root, couverture)) {
	    		nb++;
	    		solutions.add(couverture);
	    		for(Element ligne : couverture) {
	    			supprimerLigne(ligne);
	    		}
	    		couverture.clear();
	    	}
	    }
	    
	    return nb;
	}
	
	/**
	 * Donne le nombre de possibilité qu'il reste à jouer
	 * 
	 * @return
	 */
	public int getNBPossibilite() {
	    solutions = new ArrayList<List<Element>>();
		initMatrice();
		return resoudre(matrice.getMatrice());
	}
	
	public void ajoutPiece(int[] cases) {
		piecePlace.add(cases);
	}
	
	public void supprimerPiece(int[] cases) {
		piecePlace.remove(cases);
	}
}